﻿//给你一个字符串 s 和一个字符串列表 wordDict 作为字典。
//如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
//注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
//
//
//输入 : s = "leetcode", wordDict = ["leet", "code"]
//输出 : true
//解释 : 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
//
//输入 : s = "applepenapple", wordDict = ["apple", "pen"]
//输出 : true
//解释 : 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
//注意，你可以重复使用字典中的单词。
//
//
//输入 : s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出 : false
//
//提示：
//	1 <= s.length <= 300
//	1 <= wordDict.length <= 1000
//	1 <= wordDict[i].length <= 20
//	s 和 wordDict[i] 仅由小写英文字母组成
//	wordDict 中的所有字符串 互不相同

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 优化⼀：将字典⾥⾯的单词存在哈希表⾥⾯
        unordered_set<string> hash;
        for (auto& s : wordDict)
            hash.insert(s);
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;                // 保证后续填表是正确的
        s = ' ' + s;                 // 使原始字符串的下标统⼀ +1
        for (int i = 1; i <= n; i++) // 填 dp[i]
        {
            for (int j = i; j >= 1; j--) // 最后⼀个单词的起始位置
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1))) {
                    dp[i] = true;
                    break; // 优化⼆
                }
            }
        }
        return dp[n];
    }
};
